#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <fstream>

#include "GA.h"
#ifndef WIN32
#include "../F2-Sd-W/F2-Sd-W.h"
#include "../Model/lib.h"
#else
#include "..\\F2-Sd-W\\F2-Sd-W.h"
#include "..\\Model\\lib.h"
#endif
extern int 	R_0_c[n_0+1];	//需求序列类别号码

using namespace std;

int Chromosome::now_max_id=0;

int Chromosome::getID()
{
	return ID;
}


bool HasToQuit=false;


//直接设置一个染色体
void Chromosome::setChromosome(int data[])
{
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		Gene[i]=data[i];
	}
}
//随机初始化一个染色体
void Chromosome::randInit()
{
	//time_t t;
	//time(&t);
	//srand(t);
	//cout<<"n_0="<<n_0<<endl;
	//cout<<"CHROMOSOME_LENGTH="<<CHROMOSOME_LENGTH<<endl;
	//cout<<"R_0_c[]=";
	//for(int j=1;j<=CHROMOSOME_LENGTH;j++)
	//{
	//	cout<<" "<<R_0_c[j];
	//}
	//cout<<" "<<endl;
	int data[CHROMOSOME_LENGTH];
	int temp[CHROMOSOME_LENGTH][2];
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		//把R_0_c[n_0+1]随机打乱（1-based array）
		int k=i+1;
		temp[i][0]=R_0_c[k];
		//cout<<R_0_c[k]<<" ";
		temp[i][1]=-1;
	}
	//cout<<endl;
	
	/***************************
	for(int j=0;j<CHROMOSOME_LENGTH;j++)
	{
		//data[i]=?
		int L=CHROMOSOME_LENGTH-j;
		int R=rand();
		int pos=int(L*(R*1.0)/(RAND_MAX));
		if(pos<0){pos=0;}
		else if(pos>L){pos=L-1;}
		int T=temp[pos];
		//
		//std::cout<<"L="<<L<<" R="<<R<<" RMAX="<<RAND_MAX<<" pos="<<pos<<"  T="<<T<<endl;
		//
		
		for(int k=pos;k<L-1;k++)
		{
			temp[k]=temp[k+1];
		}
		temp[L-1]=-1;
		data[j]=T;
	}
	 ***************************/
	 for(int j=0;j<CHROMOSOME_LENGTH;j++)
	{
		int pos=int(CHROMOSOME_LENGTH*(rand()*1.0)/(RAND_MAX));
		while(temp[pos][1]>0){
			pos++;
			if(pos>=CHROMOSOME_LENGTH)
			{
				pos=pos%CHROMOSOME_LENGTH;
			}
		}
		data[j]=temp[pos][0];
		temp[pos][1]=1;//marked as used.
	}
	setChromosome(data);
}
//计算(实际上是目标函数值，在群体中需要处理)
double Chromosome::calcOjbectFun()
{
	obj_value=F2_Sd_W_Trail(Gene);
	return obj_value;
}
//调整目标值，用于小生境算法中惩罚相近的染色体
void Chromosome::adjustObjValue(double value)
{
	obj_value=value;
}

//get objective fuction value
double Chromosome::getObjValue()
{
	return obj_value;
}

//get the fitness value
double Chromosome::getFitness()
{
	return fitness;
}

void Chromosome::setFitness(double value)
{
	fitness=value;
}

//直接设置染色体中的一个基因
void Chromosome::setGene(int zero_based_posision, int value)
{
	Gene[zero_based_posision]=value;

}
//直接设置某一段基因的值
void Chromosome::setGene(int zero_based_position, int length, int data[])
{
	for(int i=0;i<length;i++)
	{
		Gene[zero_based_position+i]=data[i];
	}
}
//读取基因值
int Chromosome::getGene(int zero_based_position)
{
	return Gene[zero_based_position];
}
//赋值操作
void Chromosome::operator =(Chromosome& chrmsA)
{
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		Gene[i]=chrmsA.getGene(i);
	}
	fitness=chrmsA.fitness;
	obj_value=chrmsA.obj_value;
}


//变异操作
void Chromosome::mutation()//defined as two genes swape position
{
	bool flag=false;
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		if(Gene[i]<0){
			flag=true;
			break;
		}
	}
	
	time_t t;
	time(&t);
	srand(t);
	int pos1=int(CHROMOSOME_LENGTH*(1.0*rand()/RAND_MAX));
	int pos2=int(CHROMOSOME_LENGTH*(1.0*rand()/RAND_MAX));
	while(pos2==pos1){
		pos2=int(CHROMOSOME_LENGTH*(1.0*rand()/RAND_MAX));
	}
	
	if(pos1>pos2){
		int tt=pos1;
		pos1=pos2;
		pos2=tt;
	}
	int tt2[CHROMOSOME_LENGTH];
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		tt2[i]=-1;
		
	}
	for(int i=pos1;i<=pos2;i++){
		tt2[i]=Gene[i];
	}
        //int K=pos2-pos1+1;
	int p=pos1;
	for(int i=pos2;i>=pos1;i--){
		Gene[p]=tt2[i];
		if(Gene[p]<0 && (!flag)){cout<<"oppse!! a wicked number appeared"<<endl;}
		p++;
	}
	//int temp=Gene[pos1];
	//Gene[pos1]=Gene[pos2];
	//Gene[pos2]=temp;
	//std::cout<<pos1<<"<---->"<<pos2<<std::endl;
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		if(Gene[i]<0){
			cout<<"Mutation WRONG!!"<<endl;
		}
	}
}

Chromosome::Chromosome()
{
	now_max_id++;
	ID=now_max_id;

}

Chromosome::~Chromosome()
{

}

//打印
void Chromosome::show()
{
	std::cout<<"[";
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		std::cout<<Gene[i]<<"";
	}
	std::cout<<"]"<<std::endl;
	cout<<"Obj_value="<<obj_value<<endl;
}

Population::Population()
{
	Generation=0;
	for(int i=0;i<POP_SIZE;i++)
	{
		chrom[i].randInit();
	}
	for(int j=0;j<=MAX_GENERATION;j++)
	{
		theObjs[j]=-1;
	}
}
Population::~Population()
{
	
}
void Population::CrossOver(Chromosome* A, Chromosome* B)
{
	if(HasToQuit){cout<<"Now Quit CrossOver"<<endl;return;}
	//random get 2 position pos1 and pos2
	//get section SA[pos1--pos2] from pos1 to pos2 from A
	//remove the 1st SA[1] in B, the 1st SA[2] in B,...the 1st SA[i] in B
	//then get a sub sequence SB'[]
	//get the 1st 1 to pos1 in SB'[], place them before SA[], 
	//get the remain in SB', place them after SA[]
	//then a new B generated.
	//same as new A.
	int dataA[CHROMOSOME_LENGTH];
	int dataB[CHROMOSOME_LENGTH];
	int dataA2[CHROMOSOME_LENGTH];
	int dataB2[CHROMOSOME_LENGTH];
	int temp[CHROMOSOME_LENGTH];
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		dataA[i]=A->getGene(i);
		dataB[i]=B->getGene(i);
		dataA2[i]=-1;
		dataB2[i]=-1;
		temp[i]=-1;//illigle value
		if(dataA[i]<0 || dataB[i]<0)
		{
			cout<<"A negetive Gene found!(line 272)"<<endl;
			A->show();
			B->show();
			HasToQuit=true;
			return;
		}
	}
	time_t t;
	time(&t);
	srand(t);
	int pos1=int(CHROMOSOME_LENGTH*(1.0*rand()/RAND_MAX));
	int pos2=int(CHROMOSOME_LENGTH*(1.0*rand()/RAND_MAX));
	while(pos2==pos1){
		pos2=int(CHROMOSOME_LENGTH*(1.0*rand()/RAND_MAX));
	}
	int temp_i=pos1;
	if(pos1>pos2){
		pos1=pos2;
		pos2=temp_i;
	}
	//cout<<"|"<<pos1<<"<---->"<<pos2<<"|"<<endl;
	int wrong=0;
	//generate a new A into A2
		//get the section from B into temp[]
		int k=0;
		for(int i=pos1;i<=pos2;i++)
		{
			temp[i]=dataB[i];
			k++;
		}
		//remove the 1st temp[i] in A
                //int c=0;
		for(int i=pos1;i<=pos2;i++)
		{
			if(temp[i]<0){ HasToQuit=true;break;}
			int j=0;
                        //bool flag=false;
			 j=the1st(temp[i],dataA,CHROMOSOME_LENGTH);
			 if(j<0 || j>=CHROMOSOME_LENGTH){HasToQuit=true;return;}
			 dataA[j]=-1;
		}
		
		int m=0;
	/*
			for(int i=0;i<CHROMOSOME_LENGTH;i++)
			{
				if(dataA[i]>0)
				{
					dataA2[m]=dataA[i];
					m++;					
					dataA[i]=-1;
					if(m>=pos1) break;
				}
			}
			
			if(m!=pos1){cout<<"WRONG!!! m!=pos1"<<endl;}

			m=pos1;
			for(int i=0;i<CHROMOSOME_LENGTH;i++)
			{
				if(temp[i]>0){
					dataA2[m]=temp[i];
					m++;
					temp[i]=-1;						
				}
			}
			if(m!=pos2+1){cout<<"WRONG!!! m!=pos2+1(line 332)"<<endl;}

			m=pos2+1;
			for(int i=0;i<CHROMOSOME_LENGTH;i++)
			{
				if(dataA[i]>0)
				{
					dataA2[m]=dataA[i];
					m++;
					dataA[i]=-1;
				}
			}
			if(m!=CHROMOSOME_LENGTH){cout<<"WRONG!!! m!=CHROMOSOME_LENGTH(line 374)"<<endl;}
	*/ 
	for(int i=0;i<pos1;i++)
	{
		int j=the1stValid(dataA,CHROMOSOME_LENGTH);
		if(j<0 || j>=CHROMOSOME_LENGTH){HasToQuit=true;return;}
		dataA2[i]=dataA[j];
		if(dataA[j]<0 || dataA[j]>C_out){cout<<"wicked number appears.quit"<<endl;HasToQuit=true;return;}
		dataA[j]=-1;
	}
	for(int i=pos1;i<=pos2;i++)
	{
		dataA2[i]=temp[i];
		if(temp[i]<0){cout<<"wicked number appears.quit"<<endl;HasToQuit=true;return;}
	}
	for(int i=pos2+1;i<CHROMOSOME_LENGTH;i++)
	{
		int j=the1stValid(dataA,CHROMOSOME_LENGTH);
		if(j<0 || j>=CHROMOSOME_LENGTH){HasToQuit=true;return;}
		dataA2[i]=dataA[j];
		if(dataA[j]<0 || dataA[j]>C_out){cout<<"wicked number appears.quit"<<endl;HasToQuit=true;return;}
		dataA[j]=-1;
	}
		//now dataA2[] is the new A
		wrong=0;
		//generate new B into dataB2[]
		k=0;
		for(int i=0;i<CHROMOSOME_LENGTH;i++)
		{
			dataA[i]=A->getGene(i);
			dataB[i]=B->getGene(i);
			temp[i]=-1;//illigle value
			dataB2[i]=-1;
		}
		for(int i=pos1;i<=pos2;i++)
		{
			temp[i]=dataA[i];
			k++;
		}
		//remove the 1st temp[i] in B
		for(int i=pos1;i<=pos2;i++)
		{
			 int j=the1st(temp[i],dataB,CHROMOSOME_LENGTH);
			 if(j<0 || j>=CHROMOSOME_LENGTH){HasToQuit=true;return;}
			 dataB[j]=-1;
		}
		m=0;
		/*
			for(int i=0;i<CHROMOSOME_LENGTH;i++)
			{
				if(dataB[i]>0)
				{
					dataB2[m]=dataB[i];
					m++;
					dataB[i]=-1;
					if(m>=pos1)break;
				}
			}
			if(m!=pos1){cout<<"WRONG!!! m!=pos1(line 384)"<<endl;}
		
		m=pos1;
			for(int i=0;i<CHROMOSOME_LENGTH;i++)
			{
				if(temp[i]>0){
					dataB2[m]=temp[i];
					m++;
					temp[i]=-1;				
					//if(m>pos2)break;
				}
			}
			
			if(m!=pos2+1){cout<<"WRONG!!! m!=pos2+1(line 397)"<<endl;}
		m=pos2+1;
			for(int i=0;i<CHROMOSOME_LENGTH;i++)
			{
				if(dataB[i]>0)
				{
					dataB2[m]=dataB[i];
					m++;
					dataB[i]=-1;
					//if(m>CHROMOSOME_LENGTH)break;
				}
			}
			if(m!=CHROMOSOME_LENGTH){cout<<"WRONG!!! m!=CHROMOSOME_LENGTH(line 344)"<<endl;}
		//}
		 * 
	*/
	for(int i=0;i<pos1;i++)
	{
		int j=the1stValid(dataB,CHROMOSOME_LENGTH);
		if(j<0 || j>=CHROMOSOME_LENGTH){HasToQuit=true;return;}
		dataB2[i]=dataB[j];
		if(dataB[j]<0 || dataB[j]>C_out){cout<<"wicked number appears.quit"<<endl;HasToQuit=true;return;}
		dataB[j]=-1;
	}
	for(int i=pos1;i<=pos2;i++)
	{
		dataB2[i]=temp[i];
		if(temp[i]<0){cout<<"wicked number appears.quit"<<endl;HasToQuit=true;return;}
	}
	for(int i=pos2+1;i<CHROMOSOME_LENGTH;i++)
	{
		int j=the1stValid(dataB,CHROMOSOME_LENGTH);
		if(j<0 || j>=CHROMOSOME_LENGTH){HasToQuit=true;return;}
		dataB2[i]=dataB[j];
		if(dataB[j]<0 || dataB[j]>C_out){cout<<"wicked number appears.quit"<<endl;HasToQuit=true;return;}
		dataB[j]=-1;
	}
		//now new B is in dataB2[];
		for(int i=0;i<CHROMOSOME_LENGTH;i++)
		{
			if(dataA2[i]<0 || dataB2[i]<0)
			{
				cout<<"A negtive gene is appeared in a new chromosome. WRONG!!!(line 416)"<<endl;
				HasToQuit=true;return;
			}
		}
        for(int i=0;i<CHROMOSOME_LENGTH;i++)
        {
            dataA[i]=A->getGene(i);
            dataB[i]=B->getGene(i);
        }
        Chromosome tc[4];
        tc[0].setChromosome(dataA);
        tc[1].setChromosome(dataB);
        tc[2].setChromosome(dataA2);
        tc[3].setChromosome(dataB2);
        //
        tc[2].calcOjbectFun();
        tc[3].calcOjbectFun();
        SortThem(tc,4);
        //A->setChromosome(dataA2);
        //B->setChromosome(dataB2);
        (*A)=tc[0];
        (*B)=tc[1];
}

ofstream ofs2("各代最优值.txt");

void Population::CalcFitness()
{
	if(HasToQuit)return;
	//计算个体适应度值，以最大值的两倍(2*Fitness_max)为分母,fitness=2*Fitness_max-fitness;
	//chrom[POP_SIZE];
	//cout<<"calc fitness...."<<endl;
	//chrom[0].show();
	double temp=chrom[0].calcOjbectFun();
	double min_obj=temp;
	the_best_one=0;
	the_worst_one=0;
	for(int i=1;i<POP_SIZE;i++)
	{
		double f=chrom[i].calcOjbectFun();
		if(f>temp){
			temp=f;
			the_worst_one=i;
		}
		if(f<min_obj){
			the_best_one=i;
			min_obj=f;
		}
	}
	current_best_obj_value=min_obj;
	if(Generation<1){
		global_best=chrom[the_best_one];
	}
	
	//
	if(current_best_obj_value<global_best.getObjValue())
	{
		global_best=chrom[the_best_one];
	}
	
	theObjs[Generation]=global_best.getObjValue();
	ofs2<<Generation<<"\t"<<theObjs[Generation]<<endl;
	
	
	Sigma_fit=0.0;
	for(int i=0;i<POP_SIZE;i++)
	{
		double fit=2.0*temp-chrom[i].getObjValue();
		chrom[i].setFitness(fit);
		Sigma_fit=Sigma_fit+fit;//适应度总和
	}
}


//#include <vector>
void Population::Select()
//选择操作
{
    //cout<<"Select...."<<endl;
	double probs[POP_SIZE][2];//the area that chrom i occupies
	for(int i=0;i<POP_SIZE;i++)
	{
		probs[i][0]=0.0;
		probs[i][1]=0.0;//initialize
		//
		double size=chrom[i].getFitness()/Sigma_fit;
		if(i<1){
			probs[i][0]=0.0;
			probs[i][1]=probs[i][0]+size;
		}
		else{
			probs[i][0]=probs[i-1][1];
			probs[i][1]=probs[i][0]+size;
		}
	}
    //cout<<"Probabilities calced..."<<endl;
	double rand_num;
    /*
	int num[POP_SIZE];
	for(int i=0;i<POP_SIZE;i++){
		num[i]=0;
	}
    */
    /*
    num[the_best_one]++;//保存最优值
	
	//copy the global best to the current worst
    //chrom[the_worst_one]=global_best;
    num[the_worst_one]++;
	//


    //
	for(int i=2;i<POP_SIZE;){
		bool flag=false;
		rand_num=(1.0)*rand()/RAND_MAX;
		for(int j=0;j<POP_SIZE;j++){			
			if(rand_num>=probs[j][0] && rand_num<probs[j][1]){
				flag=true;
				num[j]++;
				break;
			}
			
		}
		if(flag){i++;}
	}
    cout<<"Copy numbers calced..."<<endl;
	//copy
	for(int i=0;i<POP_SIZE;)
	{
        if(num[i]>1)
        {
			for(int j=0;j<POP_SIZE;j++)
			{
				if(num[j]<1){
					
					chrom[j]=chrom[i];//copying...
					//cout<<"Chrom["<<i<<"] is copied once to Chrom["<<j<<"]"<<endl;
					num[j]++;
					num[i]--;
					if(num[j]<1){
						cout<<"MUST BE WRong!!(num["<<j<<"]="<<num[j]<<")"<<endl;
						break;
					}
				}
				if(num[i]<=1)
				{
					i++;
					break;
				}
			}
			continue;
		}
		else{
			i++;
		}
	}
    cout<<"Copied..."<<endl;
    */

    //cout<<"Begin Copy"<<endl;

    tempVector ATemp;
    ATemp.Clear();
    ATemp.Add(global_best);
    ATemp.Add(chrom[0]);

    int i=2;
    for(;i<POP_SIZE;)
    {
        bool flag=false;
        rand_num=(1.0)*rand()/RAND_MAX;
        for(int j=0;j<POP_SIZE;j++){
            if(rand_num>=probs[j][0] && rand_num<probs[j][1]){
                flag=true;
                ATemp.Add(chrom[j]);
                //cout<<"A chromosome was Selected."<<endl;
                break;
            }

        }
        if(flag){i++;}
    }
    if(i<POP_SIZE){cout<<"Selected chromosomes' number("<<i<<") less than POP_SIZE.(in Select())"<<endl;}
    ATemp.CopyTo(chrom);
    //cout<<"Copy Over"<<endl;
}

void Population::show()
{
	cout<<"\n===============\nPopulation:"<<endl;
	for(int i=0;i<POP_SIZE;i++){
		chrom[i].show();
	}
	cout<<"===============\n"<<endl;
}

void Population::test()
{
	chrom[1].show();
	chrom[2].show();
	CrossOver(&chrom[1],&chrom[2]);
	chrom[1].show();
	chrom[2].show();
	cout<<"Select Test"<<endl;
	show();
	Select();
	cout<<"after selection"<<endl;
	show();
}

void Population::main_proc()
{
	//cout<<"begin.."<<endl;
	
	CalcFitness();
	//ShowBest();
	//cout<<"begin Select()"<<endl;
	Select();
	//
	//cout<<"end Select()"<<endl;
	//cout<<"begin pairs.."<<endl;
	int index[POP_SIZE][2];
	for(int i=0;i<POP_SIZE;i++){
		index[i][0]=i;
		index[i][1]=-1;//not paired yet
	}
	int pairs[POP_SIZE/2][2];
	
	for(int i=0;i<POP_SIZE/2;i++)
	{
		pairs[i][0]=-1;//invalid
		pairs[i][1]=-1;//invalid
		//
		int pos=int(1.0*POP_SIZE*rand()/RAND_MAX);
		while(index[pos][1]>0){
			pos++;
			if(pos>=POP_SIZE){pos=pos%POP_SIZE;}
		}
		pairs[i][0]=index[pos][0];
		index[pos][1]=1;
		pos=int(1.0*POP_SIZE*rand()/RAND_MAX);
		while(index[pos][1]>0){
			pos++;
			if(pos>=POP_SIZE){pos=pos%POP_SIZE;}
		}
		pairs[i][1]=index[pos][0];
		index[pos][1]=1;
		//cout<<"a pair found.("<<pairs[i][0]<<","<<pairs[i][1]<<")"<<endl;
	}
	//cout<<"end pairs."<<endl;
	//cross it
	for(int i=0;i<POP_SIZE/2;i++)
	{
		double r1=(1.0*rand())/RAND_MAX;
		if(r1<=CROSSOVER_PROBABILITY)
		{
			CrossOver(&chrom[pairs[i][0]],&chrom[pairs[i][1]]);
			//cout<<"Chrom["<<pairs[i][0]<<"] crossovered whit Chrom["<<pairs[i][1]<<"]"<<endl;
		}
	}
	for(int i=0;i<POP_SIZE;i++)
	{
		double r2=(1.0*rand())/RAND_MAX;
		if(r2<=MUTATION_PROBABILITY)
		{
			chrom[i].mutation();
			//cout<<"Chrom["<<i<<"] is mutated."<<endl;
		}
	}
	Generation++;
}

void Population::GA()
{
	while(Generation<MAX_GENERATION)
	{
		//cout<<"G="<<Generation<<endl;
		main_proc();
	}
	cout<<".";
}

void Population::ShowBest()
{
	cout<<"Now min W(sigma)="<<current_best_obj_value<<endl;
	cout<<"Global Best is W(sigma)="<<global_best.getObjValue()<<endl;
	global_best.show();
}



//////////////////////////
//      小生境遗传算法
//////////////////////////

	//calc fitness
	//step1: memory first Niche_N chromosomes
	//step2:For POP_SIZE chromesomes
	//    select
	//    cross over
	//    mutation
	//Get New POP_SIZE chromesomes
	//combine Niche_N and POP_SIZE chromesomes together
	//calc fitness
	//calc distance
	//adjust fitness
	//Sort them and memory first Niche_N chromosomes
	//get first POP_SIZE chromesomes to new generation

ofstream fnga("NicheGA-20.txt");

void Population::NicheGA()
{
	//calc fitness
	//step1: memory first Niche_N chromosomes
	//NicheGA_main_proc()
	
	time_t startTime;
	time_t endTime;
	time(&startTime);
//    cout<<"Begin CalcFitness()"<<endl;
	CalcFitness();//ordinary calc
	SortThem(chrom,POP_SIZE);
	for(int i=0;i<Niche_N;i++)
	{
		TempChrom[i]=chrom[i];
	}
    fnga<<"\nG"<<"\t\tGlobal_best"<<endl;
	while(Generation<MAX_GENERATION+1){
        if(Generation%5==0){
			cout<<"G="<<Generation<<endl;
			ShowBest();
            fnga<<Generation<<"\t\t"<<global_best.getObjValue()<<endl;
            //fnga<<"Now min W(sigma)="<<current_best_obj_value<<endl;
            //fnga<<"Global Best is W(sigma)="<<global_best.getObjValue()<<endl;
		}
        //fnga<<Generation<<"\t\t"<<global_best.getObjValue()<<endl;
		NicheGA_main_proc();
		if(HasToQuit){cout<<"Now quit NicheGA()"<<endl;return;}
	}
	time(&endTime);
	std::cout<<"=======END===="<<std::endl;
	cout<<"Start at :"<<ctime(&startTime)<<std::endl;
	cout<<"End at :"<<ctime(&endTime)<<std::endl;
	fnga<<"=======END===="<<std::endl;
	fnga<<"Start at :"<<ctime(&startTime)<<std::endl;
	fnga<<"End at :"<<ctime(&endTime)<<std::endl;
	
}
void Population::NicheGA_main_proc()
{
	if(HasToQuit){cout<<"Now quit NicheGA_main_proc()"<<endl;return;}
	//step2:For POP_SIZE chromesomes
	//    select
	//    cross over
	//    mutation
	//Get New POP_SIZE chromesomes
	//combine Niche_N and POP_SIZE chromesomes together
	//calc fitness
	//calc distance
	//adjust fitness
	//Sort them and memory first Niche_N chromosomes
	//get first POP_SIZE chromesomes to new generation
 //   cout<<"Begin Select() in NicheGA_main_proc"<<endl;
	Select();
 //   cout<<"End Select() in NicheGA_main_proc"<<endl;
	//pair
		int index[POP_SIZE][2];
	for(int i=0;i<POP_SIZE;i++){
		index[i][0]=i;
		index[i][1]=-1;//not paired yet
	}
	int pairs[POP_SIZE/2][2];
	
	for(int i=0;i<POP_SIZE/2;i++)
	{
		pairs[i][0]=-1;//invalid
		pairs[i][1]=-1;//invalid
		//
		int pos=int(1.0*POP_SIZE*rand()/RAND_MAX);
		while(index[pos][1]>0){
			pos++;
			if(pos>=POP_SIZE){pos=pos%POP_SIZE;}
		}
		pairs[i][0]=index[pos][0];
		index[pos][1]=1;
		pos=int(1.0*POP_SIZE*rand()/RAND_MAX);
		while(index[pos][1]>0){
			pos++;
			if(pos>=POP_SIZE){pos=pos%POP_SIZE;}
		}
		pairs[i][1]=index[pos][0];
		index[pos][1]=1;
		//cout<<"a pair found.("<<pairs[i][0]<<","<<pairs[i][1]<<")"<<endl;
	}
 //   cout<<"End pairs."<<endl;
	//cross it
	for(int i=0;i<POP_SIZE/2;i++)
	{
		double r1=(1.0*rand())/RAND_MAX;
		if(r1<=CROSSOVER_PROBABILITY)
		{
            if(HasToQuit){return;}
			CrossOver(&chrom[pairs[i][0]],&chrom[pairs[i][1]]);
            //cout<<"Chrom["<<pairs[i][0]<<"] crossovered whit Chrom["<<pairs[i][1]<<"]"<<endl;
		}
	}
	for(int i=0;i<POP_SIZE;i++)
	{
		double r2=(1.0*rand())/RAND_MAX;
		if(r2<=MUTATION_PROBABILITY)
		{
			chrom[i].mutation();
			//cout<<"Chrom["<<i<<"] is mutated."<<endl;
		}
	}
 //   cout<<"CrossOver over.Mutation over."<<endl;
	//now new chromosomes generated
	CalcFitness();//ordinary calc
	//combine them to the Niche_Chrom[POP_SIZE+Niche_N]
	for(int i=0;i<POP_SIZE;i++)
	{
		if(i<Niche_N){
			Niche_Chrom[i]=TempChrom[i];
		}
		if(i<POP_SIZE)
		{
			Niche_Chrom[i+Niche_N]=chrom[i];
		}
	}
	//now combined,then calc the fitness
	//fitnesses are all calced in last CalcFitness()
	//now calc distance and adjust fitness
	//
    //
    double LL=L;
	for(int i=0;i<POP_SIZE+Niche_N;i++)
	{
		for(int j=0;j<POP_SIZE+Niche_N;j++)
		{
			if(j==i){continue;}
            if(CalcDistance(&Niche_Chrom[i],&Niche_Chrom[j])<LL)
			{
				//adjustObjValue(
				if(Niche_Chrom[i].getObjValue()>=Niche_Chrom[j].getObjValue())
				{
					Niche_Chrom[i].adjustObjValue(OBJ_PENALTY*Niche_Chrom[i].getObjValue());
				}
				else
				{
					Niche_Chrom[j].adjustObjValue(OBJ_PENALTY*Niche_Chrom[j].getObjValue());
				}
			}
		}
	}

 //   cout<<"adjust over."<<endl;
	SortThem(Niche_Chrom,POP_SIZE+Niche_N);
 //   cout<<"Sort over"<<endl;

	for(int i=0;i<POP_SIZE;i++)
	{
		chrom[i]=Niche_Chrom[i];
        //Sigma_fit+=chrom[i].getFitness();
		if(i<Niche_N)
		{
			TempChrom[i]=Niche_Chrom[i];
		}
	}
    /*
    Sigma_fit=0.0;
    double temp=-1.0;//memorize the max obj value
    for(int i=0;i<POP_SIZE;i++)
    {
        if(temp<chrom[i].getObjValue())
        {
            temp=chrom[i].getObjValue();
        }
    }
    for(int i=0;i<POP_SIZE;i++)
    {
        double fit=2.0*temp-chrom[i].getFitness();
        chrom[i].setFitness(fit);
        Sigma_fit=Sigma_fit+fit;//适应度总和
    }
    the_best_one=0;
    the_worst_one=POP_SIZE-1;
    */
	Generation++;
}

double Population::CalcDistance(Chromosome* A, Chromosome* B)
{
	double sq_sum=0.0;
	for(int i=0;i<CHROMOSOME_LENGTH;i++)
	{
		if(A->getGene(i)==B->getGene(i)){
			sq_sum+=0;
		}
		else{
			sq_sum+=1;
		}
	}
	return sq_sum;
}


void Population::SortThem(Chromosome C[], int SIZE)
{
	//sort the chrome by the fitness from big to small
	Chromosome temp;
	for(int i=0;i<SIZE-1;i++)
	{
		for(int j=i+1;j<SIZE;j++)
		{
			if(C[i].getObjValue()>C[j].getObjValue()){
				temp=C[i];
				C[i]=C[j];
				C[j]=temp;
			}
		}
	}
}

void Population::Niche_CalcFitness()
{
	//
}




////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
//////////////						////////////////////////////
//////////////		穷举试验			////////////////////////////
//////////////						////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////






//以下为与穷举相关代码

/////全排列

int K[CHROMOSOME_LENGTH];
int RS[CHROMOSOME_LENGTH];//记录最后排列
double minW_sigma=-1.0;

ofstream ofs("穷举.txt");

void clean()
{
	for (int j=0;j<CHROMOSOME_LENGTH;j++) {
		K[j]=0;
	}
}

void Init()
{
	for (int j=0;j<CHROMOSOME_LENGTH;j++) {
		K[j]=R_0_c[j+1];
		//s[j]=R_0_c[j+1];
		RS[j]=0;
	}
}

void showK()
{
	
	ofs<<"P=";
	for (int j=0;j<CHROMOSOME_LENGTH;j++) {
		ofs<<K[j]<<"";
	}
	ofs<<std::endl;
}




///把多重循环转化为递归
//这是从网上找的算法，还没弄明白！！！！
// 2009-11-17

inline void Swap(int& i,int& j)
{
	int temp=i;
	i=j;
	j=temp;
}
//Pemu全排列
bool changed=false;
long cc=0;
void Pemu(int start=0, int end=CHROMOSOME_LENGTH-1)
{
	int i;
	double temp =-1.0;
	if(start==end)
	{
		//一个排列生成了
        if(changed){
            temp=F2_Sd_W_Trail(K);
            cc++;
            changed=false;
        }
		if(minW_sigma<0 || temp<minW_sigma)
		{
			minW_sigma=temp;
			for (int j=0;j<CHROMOSOME_LENGTH;j++) {
				RS[j]=K[j];
			}
		}
	}
	else
	{
		for(i=start;i<=end;i++)
		{
            if(K[start]!=K[i]){
                Swap(K[start],K[i]);
                changed=true;
            }

                Pemu(start+1,end);

                if(K[start]!=K[i]){
                    Swap(K[start],K[i]);
                    changed=true;
                }

		}
	}
}

void RepeatPemu();

int enumeration()
{
	std::cout<<"=====穷举试验======="<<std::endl;
	
	Init();
    cc=0;
    changed=false;
	
	time_t startTime;
	time_t endTime;
	
	time(&startTime);
//	Pemu();
	RepeatPemu();
	time(&endTime);
	
    std::cout<<"cc="<<cc<<"\n=======END===="<<std::endl;
	ofs<<"Start at :"<<ctime(&startTime)<<std::endl;
	ofs<<"End at :"<<ctime(&endTime)<<std::endl;
	
	ofs<<"min W_sigma P=";
    cout<<"min W_sigma P=";
	for (int j=0;j<CHROMOSOME_LENGTH;j++) {
		ofs<<RS[j]<<"";
        cout<<RS[j]<<"";
	}
	ofs<<std::endl;
    cout<<endl;
	ofs<<"min W_sigma="<<minW_sigma<<std::endl;
    cout<<"min W_sigma="<<minW_sigma<<endl;

	return 0;
}

int the1st(int value,int data[],int length)//return the index in data[] of the element = value
{
	int rs = -1;
	for(int i=0;i<length;i++)
	{
		if(data[i]==value){
			rs=i;
			break;
		}
	}
	return rs;
}

int the1stValid(int data[],int length)//第一个合法的元素
{
	int rs = -1;
	for(int i=0;i<length;i++)
	{
		if(data[i]>0){
			rs=i;
			break;
		}
	}
	return rs;
}
/////////////////


/*
class tempVector{
    Chromosome Temp[POP_SIZE];
   public:
    void Add(Chromosome& A);
    void Clear();
    void CopyTo(Chromosome D[]);
    tempVector();
    ~tempVector();
}
*/

tempVector::tempVector()
{
    count=0;
}
tempVector::~tempVector()
{
}

void tempVector::Add(Chromosome& A)
{
    if(count>=POP_SIZE)
    {
        cout<<"[Error]:tempVector is FULL."<<endl;
        HasToQuit=true;
        return;
    }
    Temp[count]=A;
    for(int i=0;i<CHROMOSOME_LENGTH;i++)
    {
        if(Temp[count].getGene(i)<0 ||Temp[count].getGene(i)>C_out)
        {
            cout<<"tempVector::Add() failed"<<endl;
            HasToQuit=true;
            return;
            //break;
        }
    }
    count++;
    if(count>=POP_SIZE)
    {
        //cout<<"[Notice]:tempVector is FULL."<<endl;
        //cout<<".";
    }
}
void tempVector::Clear()
{
    count=0;
}

void tempVector::CopyTo(Chromosome D[])
{
    if(count<POP_SIZE)
    {
        cout<<"WARNING :tempVector 's elements("<<count<<") are less than POP_SIZE.("<<POP_SIZE<<")"<<endl;
    }
    for(int i=0;i<count;i++)
    {
        D[i]=Temp[i];
        for(int j=0;j<CHROMOSOME_LENGTH;j++){
            if(D[i].getGene(j)<0 ||D[i].getGene(j)>C_out)
            {
                cout<<"tempVector::CopyTo() failed"<<endl;
                HasToQuit=true;
                return;
                //break;
            }
        }
    }
}

//------------------------------------------
//------------------------------------------
// 4 种 q1,q2,q3,q4，有重复的全排列
//------------------------------------------
//------------------------------------------
//
//插入块的最左边有意义

void dynArray::insert(int pos,int Value)
{
    if(pos>=count)
    {
        data[count]=Value;        
    }
    else{
        for(int i=count-1;i>=pos;i--)
        {
            data[i+1]=data[i];
            data[i]=0;
        }
        data[pos]=Value;
    }
    count++;
}

int dynArray::getCount()
{
    return count;
}

dynArray::dynArray()
{
    count=0;
    for(int i=0;i<CHROMOSOME_LENGTH;i++)
    {
        data[i]=0;
    }
}
dynArray::~dynArray()
{
}

bool dynArray::isValid(int value ,int pos)
{
    if(pos>=CHROMOSOME_LENGTH || pos <0)
    {
        return false;
    }
    if(pos<1){return true;}
    else{
        if(data[pos-1]==value && data[pos]==value){
            return false;
        }
        else{
            return true;
        }
    }
}

void MyP(int q1,int q2,int q3,int q4)
{
    //int i,j,k,m;
    dynArray z;
    for(int i=0;i<q1;i++)
    {
        z.insert(i,1);
    }


}

//////////////////////

//int s[CHROMOSOME_LENGTH]={1,1,2,2,3,3,3,4,4,4};

bool cmp(int a,int b)
{
    if (a<b)
        return true;
    return false;
}
void RepeatPemu()
{
    int j,t=-1;
    int tmp=-1;
    double temp =-1.0;

    int len=CHROMOSOME_LENGTH;
    cc=1;
    //THE 1ST EXPERIMENT
    temp=F2_Sd_W_Trail(K);

    while (1) {
        int i=-1;
        for (j=len-2;j>=0;j--) {
            if (K[j]<K[j+1]) {
                i=j;
                break;
            }
        }
        if (i==-1) break;
        for (j=len-1;j>=i+1;j--) {
            if (K[j]<=K[i]) continue;
            else {
                t=j;
                tmp=K[j];
                break;
            }
        }
        K[t]=K[i];
        K[i]=tmp;
        int k=len-1-i;
        for (j=1;j<=k/2;j++) {
            t=K[i+j];
            K[i+j]=K[len-j];
            K[len-j]=t;
        }
        //puts(s);
        //for(int a=0;a<10;a++){
        //	cout<<K[a];
        //}
        //DO EXPERIMENTS

            temp=F2_Sd_W_Trail(K);
            cc++;
            
		if(minW_sigma<0 || temp<minW_sigma)
		{
			minW_sigma=temp;
			for (int j=0;j<CHROMOSOME_LENGTH;j++) {
				RS[j]=K[j];
			}
		}
	/////End of Experiment//////////////////
        //cout<<endl;
    }
}




